package two;

public class A034 {


    //合并k个有序链表
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null || lists.length==0 ) return null;
        return mergerSort(lists,0,lists.length-1);
    }

    public ListNode mergerSort(ListNode[] list,int start,int end) {
        if(start==end) return list[start];
        //if(start>end) return null;
        int mid = (start+end)>>1;
        ListNode left = mergerSort(list,start,mid);
        ListNode right = mergerSort(list,mid+1,end);
        return mergeTwoLists(left,right);
    }

    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        while(list1!=null || list2!=null) {
            if(list1!=null && list2!=null) {
                //两个都不是空
                if(list1.val < list2.val) {
                    cur.next = list1;
                    list1 = list1.next;
                    cur = cur.next;
                }
                else {
                    cur.next = list2;
                    list2 = list2.next;
                    cur = cur.next;
                }
            }else if(list2!=null) {
                //2 是非空
                cur.next = list2;
                list2 = list2.next;
                cur = cur.next;
            }else {
                cur.next = list1;
                list1 = list1.next;
                cur = cur.next;
            }
        }
        return newHead.next;
    }
}
